package solutions;

import java.util.HashMap;
import java.util.Map;

/*

Starting in the top left corner of a 2x2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20x20 grid?

Answer: 137846528820

*/


public class Euler015 {

	
	private final static int MAX_POINT = 20;
	
	private static Map<String, Long> cache = new HashMap<String, Long>();
	
	public static void main(String[] args) {
		System.out.println("Answer: " + routes(0, 0));
	}



	public static long routes(int row, int col){
		System.out.println("row: " + row + " col: " + col);
		if(row == MAX_POINT || col == MAX_POINT)
			return 1;
		
		if(cache.get(row+","+col) != null)
			return cache.get(row+","+col).longValue();
		else{
			long count = routes(row + 1, col) + routes(row, col + 1);
			cache.put(row+","+col, new Long(count));
			
			return count;
		}
	}
	
}
